﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//链表中倒数第k个结点
//描述：输入一个链表，输出该链表中倒数第k个结点
//示例：输入：1，{1，2，3，4，5};
//返回值是{5}；
//typedef struct ListNode
//{
//	int data;
//	struct ListNode* next;
//}ListNode;
//
//struct ListNode* FindKthToTail(struct ListNode* pListHead,int k)
//{
//	ListNode* fast = pListHead, * slow = pListHead;
//	while (k--)//先让fast走k步
//	{
//		if (fast == NULL)
//			return NULL;
//		fast = fast->next;
//	}
//
//	//然后slow和fast一起走
//	while (fast)
//	{
//		slow = slow->next;
//		fast = fast->next;
//	}
//	return slow;
//}
//int main()
//{
//	ListNode* n1 = (ListNode*)malloc(sizeof(ListNode));
//	assert(n1);
//	ListNode* n2 = (ListNode*)malloc(sizeof(ListNode));
//	assert(n2);
//	ListNode* n3 = (ListNode*)malloc(sizeof(ListNode));
//	assert(n3);
//	ListNode* n4 = (ListNode*)malloc(sizeof(ListNode));
//	assert(n4);
//	ListNode* n5 = (ListNode*)malloc(sizeof(ListNode));
//	assert(n5);
//	n1->data = 1;
//	n2->data = 2;
//	n3->data = 3;
//	n4->data = 4;
//	n5->data = 5;
//
//	n1->next = n2;
//	n2->next = n3;
//	n3->next = n4;
//	n4->next = n5;
//	n5->next = NULL;
//
//
//	ListNode* plist = FindKthToTail(n1,8);
//	while (plist)
//	{
//		printf("%d->", plist->data);
//		plist = plist->next;
//	}
//	printf("\n");
//	free(plist);
//	plist = NULL;
//	return 0;
//}



//相交链表
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null.
//intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
//listA - 第一个链表
//listB - 第二个链表
//skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
//skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

//思路1：尾结点是否相等，尾结点相等就是相交
//思路2：找交点
//a.A链表所有结点跟B链表都比较遍历一遍，相等的那个就是交点
//时间复杂度：O(N^2) / O(N*M)
//要求优化到O(N)  ⬇
//b.分别求出两个链表的长度LA和LB，长的先走abs(LA-LB)步，再同时走，第一个相等就是相交。

//struct ListNode
//{
//	int data;
//	struct ListNode* next;
//};
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//	struct ListNode* tailA = headA;
//	struct ListNode* tailB = headB;
//	int lenA = 1;
//	int lenB = 1;
//	//找尾
//	while (tailA->next)
//	{
//		tailA = tailA->next;
//		++lenA;
//	}
//	while (tailB->next)
//	{
//		tailB = tailB->next;
//		++lenB;
//	}
//	if (tailA != tailB)
//	{
//		return NULL;
//	}
//
//	//计算长度
//	int gap = abs(lenA - lenB);
//	struct ListNode* longList = headA;
//	struct ListNode* shortList = headB;
//	if (lenA < lenB)
//	{
//		longList = headB;
//		shortList = headA;
//	}
//
//	while (--gap)
//	{
//		longList = longList->next;
//	}
//	while (longList != shortList)
//	{
//		longList = longList->next;
//		shortList = shortList->next;
//	}
//	return longList;
//}




//环形链表
//给你一个链表的头节点 head ，判断链表中是否有环。
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
//为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
//注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
//如果链表中存在环 ，则返回 true 。 否则，返回 false 。


//问题：
//1.slow和fast一定会相遇吗？
//2.slow走1步，fast走n（3/4/5……）步可以吗？（n>2）
//请证明！
//1.一定会相遇，在slow一次走一步，fast一次走两步的情况
//fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N。
//slow进环以后，fast开始追击slow,slow每走1步，fast每走2步，它们之间距离缩小1，
//追击过程中，它们之间的距离变化。
//N ， N - 1， N - 2,……，2，1，0

//slow一次走1步
//fast一次走3步
//1.slow和fast一定会相遇吗？  不一定
//fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N，
//slow进环以后，fast开始追击，slow每走1步，fast每走3步，它们之间的距离缩小2
//N->偶数
//N ,N - 2 , N - 4,……,4,2,0 -》相遇
//N ->奇数
//N ,N-2,N-4,N-6,……，3，1，-1  -》错过
//进入新一轮的追击
//slow和fast的距离变成C-1（假设C是环的长度）
//如果C-1是偶数那么下一轮可以追上
//如果C-1是奇数那么永远追不上


//思路：一个指针从相遇点走，一个指针从链表头开始，它们会在入口点相遇。
//fast走的路程是slow的2倍
//假设
//链表头--环入口点距离：L
//环入口点 -- 相遇点距离：X
//环的长度：C
//slow走的路程是多少：L+X
//fast走的路程是多少：L+n*C+X(n是slow进环前，假设fast在环里面转的圈数)
//分析：有没有可能slow进环转了几圈才追上？
//不可能！1圈之内，fast必然追上slow,因为它们之间距离每次缩小1，不会错过，slow走1圈，fast都走了2圈，肯定追上了。

//结论：2(L+X) = L+n*C+X
//L + X = n * C
//L     = n*c - X
//n等于1是它的一个特例


